class MonotonicQueue:
    from collections import deque

    def __init__(self, type):
        self.type = type == 'decrease'

        self.queue = self.deque()
    
    def head(self):
        return self.queue[0]
    
    def is_monotonic(self, x):
        tail = self.queue[-1]

        return tail >= x if self.type else tail <= x

    def push(self, x):
        while self.queue and not self.is_monotonic(x):
            self.queue.pop()

        self.queue.append(x)
    
    def pop(self, value):
        if self.head() == value:
            self.queue.popleft()


class Solution:
    def maxSlidingWindow(self, nums, k):
        decrease_queue = MonotonicQueue('decrease')
        maxs = []

        for i in range(k):
            decrease_queue.push(nums[i])
        maxs.append(decrease_queue.head())

        for new_right in range(k, len(nums)):
            old_left = nums[new_right - k]

            decrease_queue.pop(old_left)
            decrease_queue.push(nums[new_right])

            maxs.append(decrease_queue.head())
        
        return maxs